1. Field of the Invention
Implementations consistent with principles of the invention relate generally to data lookup, and more particularly, to data lookup using linked lists.
2. Description of Related Art
A hashed linked list is a widely used data structure for databases with long access keys. A lookup into such a database typically requires a recursive search into the hashed linked list. Each phase of the recursive search requires a matching comparison of a key with data in the linked list. Such a process requires multiple accesses to external memories and multiple compare instructions, and usually requires a large number of instructions when implemented in typical reduced instruction set computer (RISC) central processing unit (CPU) instructions. Therefore, typical software implemented hashed linked list traversal may be problematic when program space is at a premium (e.g., in instances where the entire program is stored on-chip).